package lc46;
//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//
//
// 示例 2：
//
//
//输入：nums = [0,1]
//输出：[[0,1],[1,0]]
//
//
// 示例 3：
//
//
//输入：nums = [1]
//输出：[[1]]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 6
// -10 <= nums[i] <= 10
// nums 中的所有整数 互不相同
//
// Related Topics 数组 回溯 👍 1601 👎 0

import utils.IntArrOneFactory;

import java.util.ArrayList;
import java.util.List;

/**
 * 46. 全排列
 * <a href="https://leetcode-cn.com/problems/permutations/"/>
 * index=1
 * time:O(n×n!)
 * space:O(n)
 * spend:15m
 */
class Solution {

    List<List<Integer>> ans = new ArrayList<>();

    int[] nums1;

    public List<List<Integer>> permute(int[] nums) {
        nums1 = nums;
        int[] visited = new int[nums.length];
        backTrack(new ArrayList<>(), visited);
        return ans;
    }

    public void backTrack(List<Integer> temp, int[] visited) {
        // 完成条件 所有数都填完
        if(temp.size() == nums1.length){
            ans.add(new ArrayList<>(temp));
            return;
        }
        for(int i = 0; i < nums1.length; i++){
            if(visited[i] == 1){
                continue;
            }
            visited[i] = 1;
            temp.add(nums1[i]);
            backTrack(temp, visited);
            visited[i] = 0;
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> permute = solution.permute(new IntArrOneFactory().produce("[1,2,3]"));
        System.out.println(permute);
    }

}
